package simple;

import data.ListNode;

import java.util.TreeSet;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/5/7 21:55
 */
public class No83_删除排序链表中的重复元素 {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        listNode.add(6);
        listNode.add(6);
        listNode.add(7);
        listNode.add(7);
        listNode.add(7);
        listNode.add(7);
        listNode.add(9);
        listNode.add(9);
        listNode.add(9);
        Solution83 solution83 = new Solution83();
        ListNode result = solution83.deleteDuplicates(listNode);
        System.out.println();
    }
}

class Solution83 {
    public ListNode deleteDuplicates(ListNode listNode) {
        //快慢指针
        //头
        ListNode head = new ListNode(-1);
        head.next = listNode;

        //保存头
        ListNode headCp = head;

        //初始化红指针
        ListNode red = new ListNode(-1);
        ListNode green = head.next;

        while (green != null) {
            if (red.val != green.val) {
                //红指针指向绿指针
                red.next = green;
                //红指针到绿指针,绿指针往后移
                red = red.next;
            }
            green = green.next;
        }
        red.next = null;

        //刷回去
        head = headCp;
        return head.next;
    }
}

    //public ListNode deleteDuplicates(ListNode listNode) {
    //    //双指针
    //    //维护头
    //    ListNode head = new ListNode(-1);
    //    head.next = listNode;
    //    //保存头
    //    ListNode headCp = head;
    //
    //    ListNode red = head.next;
    //    if (red == null) {
    //        return null;
    //    } else if (red.next == null) {
    //        return red;
    //    }
    //    ListNode green = red.next;
    //
    //
    //    //操作
    //    while (green != null) {
    //        if (red.val != green.val) {
    //            green = green.next;
    //            red = red.next;
    //        } else {
    //            green = green.next;
    //            red.next = green;
    //        }
    //    }
    //
    //    //刷回去
    //    head = headCp;
    //    return head.next;
    //}

    //public ListNode deleteDuplicates(ListNode head) {
    //    //鸡贼法,TreeSet
    //    TreeSet<Integer> treeSet = new TreeSet<>();
    //    while (head != null) {
    //        int data = head.val;
    //        treeSet.add(data);
    //        head = head.next;
    //    }
    //    //treeSet://1,6,7,9
    //
    //    //遍历treeSet加回去
    //    ListNode result = new ListNode(-1);
    //    for (int set : treeSet) {
    //        addList(result, set);
    //    }
    //    return result.next;
    //}
    //
    //public void addList(ListNode head, int data) {
    //    ListNode headCp = head;
    //    while (head != null && head.next != null) {
    //        head = head.next;
    //    }
    //    head.next = new ListNode(data);
    //    head = headCp;
    //}